977. 有序数组的平方

Similar Question

Solution Tips

方案一: 暴力法

第一次遍历, 做平方, 然后排序即可

方案二: 双指针

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i 指向起始位置，j 指向终止位置。

定义一个新数组 result，和 A 数组一样的大小，让 k 指向 result 数组终止位置。

如果 A[i] * A[i] < A[j] * A[j] 那么 result[k--] = A[j] * A[j];

如果 A[i] * A[i] >= A[j] * A[j] 那么 result[k--] = A[i] * A[i];

var sortedSquares = function(nums) {
    let n = nums.length;
    let res = new Array(n).fill(0);
    let i = 0, j = n - 1, k = n - 1;
    while (i <= j) {
        let left = nums[i] * nums[i],
            right = nums[j] * nums[j];
        if (left < right) {
            res[k--] = right;
            j--;
        } else {
            res[k--] = left;
            i++;
        }
    }
    return res;
};

可以理解为是利用了对撞指针做 reverse